// https://leetcode.cn/problems/implement-stack-using-queues/

// 题干：请你仅使用两个队列实现一个后入先出（LIFO）的栈
//      并支持普通栈的全部四种操作（push、top、pop 和 empty）实现 MyStack 类

// 示例：输入：["MyStack", "push", "push", "top", "pop", "empty"]
//[[], [1], [2], [], [], []]
//      输出：[null, null, null, 2, 2, false]

#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

typedef int QDataType;
typedef struct QueueNode
{
    struct QueueNode* next;
    QDataType data;
}QNode;

typedef struct Queue
{
    QNode* head;
    QNode* tail;
}Queue;

// 初始化
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);

// 队尾入,队头出
void QueuePush(Queue* pq, QDataType val);
void QueuePop(Queue* pq);

// 获取数据，判断是否为空
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
int QueueSize(Queue* pq);
bool isQueueEmpty(Queue* pq);

void QueueInit(Queue* pq)
{
    assert(pq);

    pq->head = pq->tail = NULL;
}

void QueueDestroy(Queue* pq)
{
    assert(pq);

    QNode* cur = pq->head;
    while (cur != NULL) {
        QNode* next = cur->next;
        free(cur);
        cur = next;
    }
    pq->head = pq->tail = NULL;
}

void QueuePush(Queue* pq, QDataType val)
{
    assert(pq);

    QNode* newNode = (QNode*)malloc(sizeof(QNode));
    if (newNode == NULL) {
        printf("malloc fail\n");
        exit(-1);
    }

    newNode->data = val;
    newNode->next = NULL;

    if (pq->tail == NULL) {
        pq->head = pq->tail = newNode;
    }
    else {
        pq->tail->next = newNode;
        pq->tail = newNode;
    }
}

void QueuePop(Queue* pq)
{
    assert(pq);
    assert(pq->head);

    if (pq->head->next == NULL)
    {
        free(pq->head);
        pq->head = pq->tail = NULL;
    }
    else {
        QNode* next = pq->head->next;
        free(pq->head);
        pq->head = next;
    }
}

QDataType QueueFront(Queue* pq)
{
    assert(pq);
    assert(pq->head);

    return pq->head->data;
}

QDataType QueueBack(Queue* pq)
{
    assert(pq);
    assert(pq->head);

    return pq->tail->data;
}

int QueueSize(Queue* pq)
{
    assert(pq);

    int size = 0;
    QNode* cur = pq->head;
    while (cur != NULL) {
        size++;
        cur = cur->next;
    }

    return size;
}

bool isQueueEmpty(Queue* pq)
{
    assert(pq);

    return pq->head == NULL;
}


typedef struct {
    Queue q1;
    Queue q2;

} MyStack;


MyStack* myStackCreate()
{
    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);

    return pst;
}

int myStackPop(MyStack* obj)
{
    Queue* emptyQ = &obj->q1;
    Queue* nonemptyQ = &obj->q2;

    if (QueueSize(emptyQ)) {
        emptyQ = &obj->q2;
        nonemptyQ = &obj->q1;
    }

    while (QueueSize(nonemptyQ) > 1) {
        QueuePush(emptyQ, QueueFront(nonemptyQ));
        QueuePop(nonemptyQ);
    }

    int top = QueueFront(nonemptyQ);
    QueuePop(nonemptyQ);

    return top;
}

void myStackPush(MyStack* obj, int x)
{
    if (!isQueueEmpty(&obj->q1)) {
        QueuePush(&obj->q1, x);
    }
    else QueuePush(&obj->q2, x);
}

int myStackTop(MyStack* obj)
{
    int ret;
    if (!isQueueEmpty(&obj->q1)) {
        ret = QueueBack(&obj->q1);
    }
    else ret = QueueBack(&obj->q2);

    return ret;
}

bool myStackEmpty(MyStack* obj)
{
    return isQueueEmpty(&obj->q1) && isQueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj)
{
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);

    free(obj);
    obj = NULL;
}

int main()
{
    MyStack* pst = myStackCreate();

    myStackPush(pst, 1);
    myStackPush(pst, 2);
    myStackPush(pst, 3);

    printf("头部元素是：%d\n", myStackTop(pst));
    printf("开始出栈了！\n");
    while (!myStackEmpty(pst)) {
        int top = myStackTop(pst);
        printf("%d ", top);

        myStackPop(pst);
    }
    myStackFree(pst);

    return 0;
}